package com.cctc.juc.source.Bitc.Icontainer.hash;

import java.util.AbstractMap;
import java.util.concurrent.ConcurrentMap;

/**
 * [ConcurrentHashMap（JDK 8，常用）线程安全的哈希表]
 * 要求：熟练掌握（手撕、陈述）ConcurrentHashMap [（JDK 8）线程安全的哈希表] 核心（主干）实现逻辑。
 * 概述：JDK 8 中的 ConcurrentHashMap 为了进一步提高并发效率，放弃了 JDK 7 中的 Segment 分段锁机制，而是将并发粒度进一步细化，内部数据实现完全复用普通 HashMap 的代码，并在此基础上利用 cas “自旋” 操作 + synchronized 关键字组合的方式将 HashMap 的代码进行线程安全重构，即以 cas “自旋” 方式原子操作每个哈希槽，当出现哈希冲突时，再使用 synchronized 内置锁（每个哈希槽的线程争用通常不会太激烈，因此此处通常为 synchronized 偏向锁或轻量级锁）互斥访问哈希槽中的的单向链表或红黑树，将并发粒度细化到了每个哈希槽，即解决了哈希表的线程安全问题，又最大限度地提升了并发量。
 * 面试题：JDK 8 中的 ConcurrentHashMap 为什么不使用 ReentrantLock 显式锁而使用 cas + synchronized 组合来解决线程安全问题呢？？？
 * - 首先，如果为每个哈希槽创建一个 ReentrantLock 实例，会带来非常大的内存开销；
 * - 其次，尽管对同一个哈希表的线程争用会非常激烈，但是对同一个哈希表内的每个哈希槽的线程争用通常不会太激烈，所以使用 cas “自旋” + synchronized 偏向锁或轻量级锁并不会降低 ConcurrentHashMap 的性能，且内存开销微乎其微。
 */
public abstract class DC8HMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {
    /**
     * [Node 数据节点（数据模型）] 内部类。
     * - 单向链表，只有 next 后继节点。
     */
    static class Node<K, V> implements Entry<K, V> {
        final int hash;
        final K key;
        volatile V value;
        volatile Node<K, V> next;

        public Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }

        @Override
        public V setValue(V value) {
            throw new UnsupportedOperationException();
        }

        @Override
        public String toString() {
            return key + "=" + value;
        }

        @Override
        public int hashCode() {
            return key.hashCode() ^ value.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == this) return true;
            if (obj instanceof Entry) {
                Entry entry = (Entry) obj;
                if (entry.getKey().equals(key) && entry.getValue().equals(value)) {
                    return true;
                }
            }
            return false;
        }
    }

    volatile transient Node<K, V>[] table;
    volatile private transient int size;

    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4, DEFAULT_CONCURRENCY_LEVEL = 16, MAXIMUM_CAPACITY = 1 << 30;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8, MIN_TREEIFT_CAPACITY = 64, UNTREEIFY_THRESHOLD = 6;

    public DC8HMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
        if (initialCapacity < 0 || loadFactor <= 0 || concurrencyLevel <= 0) throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel) initialCapacity = concurrencyLevel;
        long size = (long) (1.0 + (long) initialCapacity / loadFactor);
        int capacity = size >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : tableSizeFor(size);
        this.size = capacity;
    }

    private static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n < 0 ? 1 : n >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : n + 1;
    }

    static final int hash(int h) {
        // 0x7fffffff，Node 节点哈希常量
        return (h ^ (h >>> 16)) & 0x7fffffff;
    }

    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /**
     * 以（线程安全）写（插入 | 更新）操作方法为例，分析 ConcurrentHashMap [JDK 8] 底层线程同步原理。
     * 核心（实现）逻辑：
     * 1）如果 table 数组尚未初始化，调用 initTable() 方法，执行初始化操作；
     * 2）基于关键字 key 的散列值，定位目标节点在 table 数组中的位置（下标），获取根节点；
     * 3）如果根节点不存在，则基于 CAS 操作以线程安全的方式创建，作为新插入节点，然后直接走 6）；
     * 4）如果根节点存在，则基于 synchronized(根节点) 内置锁，以线程安全的方式执行写（插入 | 更新）操作：
     * 4.1）如果根节点是链表节点，则遍历链表，寻找目标节点：
     * - 如果找到目标节点，则更新目标节点的 value 值，直到成功，走 5）；
     * - 否则，则创建一个新节点插入到链表尾部，作为新插入节点，走 5）；
     * 4.2）如果根节点是红黑树节点，则调用 putTreeVal() 方法，执行红黑树写操作，更新目标节点的 value 值，走 5）；
     * 5）如果 4）插入新节点后，链表长度（Node 节点数量）达到了树化阈值（TREEIFY_THRESHOLD [8]），则调用 treeifyBin() 方法，将链表转化成红黑树，提升读写效率；如果  4）为更新操作，操作结束，直接返回旧元素值；否则继续走 6）；
     * 6）更新数组大小（节点数量）；
     * 7）插入操作结束，返回 null；
     *
     * @param key          关键字
     * @param value        元素值
     * @param onlyIfAbsent 是否只进行插入操作？
     * @return 如果是插入操作，返回 null；如果是更新操作，返回旧元素值。
     */
    private V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = hash(key.hashCode());
        int binCount = 0;
        for (Node<K, V>[] tab = table; ; ) {
            Node<K, V> parent;
            int n;
            int index;
            int phash;
            if (tab == null || (n = tab.length) == 0) {
                tab = initTable();
            } else if (parent = tabAt(tab, index = hash & (n - 1)) == null) {
                if (casTabAt(tab, index, null, new Node<K, V>(hash, key, value, null))) {
                    break;
                }
            } else if ((phash = parent.hash) == MOVED) {
                tab = helpTransfer(tab, parent);
            } else {
                V oldValue = null;
                synchronized (parent) {
                    if (tabAt(tab, index) == parent) {
                        if (phash >= 0) {
                            binCount = 1;
                            for (Node<K, V> entry = parent; ; ++binCount) {
                                K k;
                                if (entry.hash == hash && ((k = entry.key) == key || (key != null && key.equals(k)))) {
                                    oldValue = entry.value;
                                    if (!onlyIfAbsent || oldValue == null) entry.value = value;
                                    break;
                                }
                                Node<K, V> prev = entry;
                                if ((entry = entry.next) == null) {
                                    prev.next = new Node<>(hash, key, value, null);
                                    break;
                                }
                            }
                        }
                    } else if (parent instanceof TreeBin) {
                        binCount = 2;
                        Node<K, V> target = ((TreeBin<K, V>) parent).putTreeVal(hash, key, value);
                        if (target != null) {
                            oldValue = target.value;
                            if (!onlyIfAbsent || oldValue == null) target.value = value;
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, index);
                    if (oldValue != null) return oldValue;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

    // ... ...

}
